//
// Created by wdq on 22-9-16.
//
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int head;
    int tail;
    int weight;

    Edge() = default;

    Edge(int head, int tail, int weight) : head(head), tail(tail), weight(weight) {}


};


struct ALGraph {

    vector<Edge *> *edges;
    int edgeNum;
    int vexNum;
    const char *names;

    explicit ALGraph(const char *names) {
        this->edgeNum = 0;
        this->vexNum = int(strlen(names));
        this->names = names;
        this->edges = new vector<Edge *>();

    }

    void addArc(int head, int tail, int weight = 0) const {
        edges->emplace_back(new Edge(head, tail, weight));
    }

    void output() const {
        for (auto &i: *edges) {
            cout << names[i->head] << " -> " << names[i->tail] << endl;
        }
    }

    void output(Edge *edge) const {
        cout << names[edge->head] << " -> " << names[edge->tail] << " : " << edge->weight << endl;
    }
};

struct UnionFind {
    int *pre;
    int size;

    explicit UnionFind(int size = 10) {
        this->size = size;
        this->pre = new int[size];
        for (int i = 0; i < size; i++) {
            pre[i] = i;
        }

    }

    ~UnionFind() {
        delete[]pre;
    }

    int find(int x) {
        return pre[x] == x ? x : pre[x] = find(pre[x]);
    }

    void merge(int x, int y) {
        this->pre[find(x)] = this->find(y);

    }

    bool isSame(int x, int y) {
        return find(x) == find(y);
    }

};


void kruskal(ALGraph &G) {
    sort(G.edges->begin(), G.edges->end(), [](Edge *&x, Edge *&y) -> bool { return x->weight < y->weight; });
    UnionFind set(G.vexNum);
    for (auto &edge: *G.edges) {
        if (!set.isSame(edge->head, edge->tail)) {
            G.output(edge);
            set.merge(edge->head, edge->tail);
        }
    }

}


int main() {
    const char *p = "abcdef";
    ALGraph g(p);
    g.addArc(0, 1, 6);
    g.addArc(0, 3, 5);
    g.addArc(0, 2, 1);
    g.addArc(1, 2, 5);
    g.addArc(1, 4, 3);
    g.addArc(2, 4, 6);
    g.addArc(2, 3, 5);
    g.addArc(2, 5, 4);
    g.addArc(3, 5, 2);
    g.addArc(4, 5, 6);
//    g.output();
    cout << "kruskal: " << endl;
    kruskal(g);


    return 0;
}